/*
 * Grafo.java
 *
 * Criado em 1 de Junho de 2007, 19:40
 */

package dharsudoku.core.grafo;

import dharsudoku.core.vertice.Vertice;
import dharsudoku.core.vertice.VerticeCartesiano;

/**
 * Implementa um grafo não direcionado, sem loops, sem duplas arestas e
 * sem pesos.
 * @author Rodrigo
 */
public class Grafo {
    
    private java.util.Set vertices;
    
    /**
     * Cria um grafo vazio
     */
    public Grafo() {
	vertices = new java.util.HashSet();
    }
    
    /**
     * Adiciona um vértice ao grafo
     * @param vertice Vértice a ser adicionado
     */
    public void adicionar(Vertice vertice) {
	if (!vertices.contains(vertice))
	    vertices.add(vertice);
    }
    
    /**
     * Cria uma aresta não direcional no grafo entre dois vértices
     * @param A vértice A
     * @param B vértice B
     * @throws Exception Se houver uma tentativa de criar loops
     */
    public void adicionarAresta(Vertice A, Vertice B) throws Exception {
	A.ligar(B);
    }
    
    /**
     * Remove um vértice do grafo
     * @param vertice Vértice a ser removido
     */
    public void remover(Vertice vertice) {
	if (vertices.contains(vertice)) {
	    vertices.remove(vertice);
	}
    }
    
    /**
     * Remove aresta, se existir, entre dois vértices do grafo
     * @param A vértice A
     * @param B vértice B
     */
    public void removerAresta(Vertice A, Vertice B) {
	A.desligar(B);
    }
    
    /**
     * Retorna tamanho do grafo
     * @return Tamanho do grafo(número de vértices)
     */
    public int getTamanho() {
	return vertices.size();
    }
    
    /**
     * Limpa grafo. Remove todos os vértices
     */
    public void clear() {
	vertices.clear();
    }
    
    /**
     * Retorna vértices do grafo
     * @return Conjunto de vértices do grafo
     */
    public java.util.Set getVertices() {
	return vertices;
    }
    
    /**
     * Verifica se existe vértice no grafo
     * @param vertice Vertice a ser verificado a pertinencia
     * @return Verdadeiro se grafo contém vertice
     */
    public boolean possui(Vertice vertice) {
	return vertices.contains(vertice);
    }
    
    /**
     * Verifica se existe uma aresta no grafo
     * @param A Inicio da aresta
     * @param B Fim da aresta
     * @return Verdadeiro se aresta existe no grafo
     */
    public boolean possuiAresta(Vertice A, Vertice B) {
	return (vertices.contains(A) && vertices.contains(B) && A.isAdjacente(B));
    }
    
    /**
     * Verifica quantas conexões este grafo
     * faz com um vértice
     *
     * @param vertice Vértice a ser validada conexoes
     * @return Número de conexões(arestas)
     */
    public int conexoes(Vertice vertice) {
	int conexoes = 0;
	
	/* Percorre vertices deste grafo */
	for (java.util.Iterator i = this.vertices.iterator(); i.hasNext(); ) {
	    Vertice v = (Vertice)i.next();
	    
	    if (v.isAdjacente(vertice))
		conexoes++;
	}
	
	return conexoes;
    }
    
    /**
     * Verifica quantas conexões este grafo
     * faz com um vértice, mas que nao seja adjacente 
     * a um outro grafo
     *
     * @param vertice Vértice a ser validada conexoes
     * @param A Outro grafo
     * @return Número de conexões(arestas)
     */
    public int conexoes(Vertice vertice, Grafo A) {
	int conexoes = 0;
	
	/* Percorre vertices deste grafo */
	for (java.util.Iterator i = this.vertices.iterator(); i.hasNext(); ) {
	    Vertice v = (Vertice)i.next();
	    
	    if (v.isAdjacente(vertice) && !A.existeConexao(v))
		conexoes++;
	}
	
	return conexoes;
    }
    
    /**
     * Verifica se algum vértice deste grafo se
     * conecta a um dado vértice
     *
     * @param vertice Vértice a ser validada conexoes
     * @return Verdadeiro se existe conexão com o vértice
     */
    public boolean existeConexao(Vertice vertice) {
	
	/* Percorre vertices deste grafo */
	for (java.util.Iterator i = this.vertices.iterator(); i.hasNext(); ) {
	    Vertice v = (Vertice)i.next();
	    
	    if (v.isAdjacente(vertice))
		return true;
	}
	
	return false;
    }
    
    /**
     * Verifica se um grafo é independente
     * @param Verdadeiro se é independente
     */
    public boolean isIndependente() {
	
	/* Percorre vertices deste grafo */
	for (java.util.Iterator i = this.vertices.iterator(); i.hasNext(); ) {
	    Vertice v = (Vertice)i.next();
	    
	    if (this.existeConexao(v))
		return false;
	}
	
	return true;
    }
    
    /**
     * Retorna um grafo formado de VerticeCartesiano que é
     * o produto cartesiano deste com um outro grafo.
     * @param grafo Segundo grafo
     * @return Produto cartesiano deste com o segundo grafo
     */
    public Grafo getProdutoCartesiano(Grafo grafo) {
	
	Grafo p = new Grafo();
	int c = 0;
	
	/* Cria e adiciona todos os vértices em p */
	for (java.util.Iterator i = this.vertices.iterator(); i.hasNext(); ) {
	    Vertice A = (Vertice)i.next();
	    
	    for (java.util.Iterator j = grafo.vertices.iterator(); j.hasNext(); ) {
		Vertice B = (Vertice)j.next();
		
		p.adicionar(new VerticeCartesiano(A, B, ++c));
	    }
	}
	
	/* Percorre vertices em P e realiza ligações de arestas */
	for (java.util.Iterator i = p.vertices.iterator(); i.hasNext(); ) {
	    VerticeCartesiano A = (VerticeCartesiano)i.next();
	    
	    for (java.util.Iterator j = p.vertices.iterator(); j.hasNext(); ) {
		VerticeCartesiano B = (VerticeCartesiano)j.next();
		
		if ((A != B) && (
			(A.getU() == B.getU() && A.getV().isAdjacente(B.getV())) ||
			(A.getV() == B.getV() && A.getU().isAdjacente(B.getU())))) {
		    try {
			A.ligar(B);
		    } catch (Exception ex) {
			continue;
		    }
		}
	    }
	}
	
	return p;
    }
    
    /**
     * Efetua a disjunção entre grafos
     * @param grafo Segundo grafo
     * @return Disjunção entre este e segundo grafo
     */
    public Grafo getDisjuncao(Grafo grafo) {
	Grafo disjuncao = new Grafo();
	
	/* Percorre vertices deste grafo */
	for (java.util.Iterator i = this.vertices.iterator(); i.hasNext(); ) {
	    Vertice v = (Vertice)i.next();
	    
	    if (!grafo.possui(v))
		disjuncao.adicionar(v);
	}
	
	/* Percorre vertices do segundo grafo */
	for (java.util.Iterator j = grafo.vertices.iterator(); j.hasNext(); ) {
	    Vertice u = (Vertice)j.next();
	    
	    if (!this.possui(u))
		disjuncao.adicionar(u);
	}
	
	return disjuncao;
    }
    
    /**
     * Efetua a interseccao entre grafos
     * @param grafo Segundo grafo
     * @return Interseccao entre este e segundo grafo
     */
    public Grafo getInterseccao(Grafo grafo) {
	
	Grafo interseccao = new Grafo();
	
	/* Percorre vertices deste grafo */
	for (java.util.Iterator i = this.vertices.iterator(); i.hasNext(); ) {
	    Vertice v = (Vertice)i.next();
	    
	    if (grafo.possui(v))
		interseccao.adicionar(v);
	}
	
	return interseccao;
    }
    
    /**
     * Efetua a união entre grafos
     * @param grafo Segundo grafo
     * @return União entre este e segundo grafo
     */
    public Grafo getUniao(Grafo grafo) {
	
	Grafo uniao = new Grafo();
	
	/* Percorre vertices deste grafo */
	for (java.util.Iterator i = this.vertices.iterator(); i.hasNext(); ) {
	    Vertice v = (Vertice)i.next();
	    uniao.adicionar(v);
	}
	
	/* Percorre vertices do segundo grafo */
	for (java.util.Iterator j = grafo.vertices.iterator(); j.hasNext(); ) {
	    Vertice u = (Vertice)j.next();
	    uniao.adicionar(u);
	}
	
	return uniao;
    }
    
    /**
     * Verifica se existe somente uma conexão entre um
     * vértice e este grafo
     *
     * @param v Vértice
     * @return Vertice do grafo que é o único adjacente ao vértice, ou nulo se não existe uma única conexoes.
     */
    public Vertice getUnicaConexao(Vertice v) {
	
	Vertice conexao = null;
	
	/* Percorre todo conjunto de vertices de S */
	for (java.util.Iterator i = this.getVertices().iterator(); i.hasNext(); ) {
	    Vertice u = (Vertice)i.next();
	    
	    if (u.isAdjacente(v)) {
		if (conexao != null)
		    return null;
		conexao = u;
	    }
	}
	
	return conexao;
    }
    
}
